package com.gorkr;

import org.junit.jupiter.api.Test;

/**
 * 矩阵连乘 （没找到leetcode上是那个题)
 */
public class Strassen {

    // dp[i][j] 表示Ai...Aj相乘最小计算次数
    private int dp[][];

//    // s[i][j]=k 表示dp[i][j] 的最后一次划分 dp[i][k] 和 dp[k+1][j]
//    private int s[][];

    // 输入
    private int p[];


    public Strassen() {
        p = new int[]{20, 30, 15, 10, 50};
        dp = new int[5][5];
//        s = new int[4][4];

    }

    public int matrixChain(){
        int n = dp.length; // 矩阵数量
        // base case 单个矩阵情况
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }

        for(int len=2; len<=n; len++){  // 计算长度为len的矩阵链最优解
            for(int i =1; i<n-len+1; i++){  // 矩阵链的开始下标
                int j = i+len-1;  // 矩阵链的结束下表
                dp[i][j] = Integer.MAX_VALUE;
                for(int k=i; k<j; k++){  // 枚举划分位置
                    int tmp = dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j];  // 为什么是p[j]
                    dp[i][j] = Math.min(dp[i][j],tmp);
                }

            }

        }
        return dp[1][dp.length-1];

    }

    @Test
    public void test(){
        Strassen strassen = new Strassen();
        System.out.println( strassen.matrixChain());
    }


}
